/*
 * Project: Code
 * File Created at 2024/1/14
 @Type Word_Break.java
 @author Goodwin
 * Website : https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-100-liked
*/

package Dynamic_Program;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Word_Break {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wds = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length()+2];
        dp[0] = true;
        for (int i = 1; i < s.length()+1; i++) {
            for (int j = 0; j < i; j++) {
                if(dp[j] && wds.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
